import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution01 {
	public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
				new Comparator<int[]>() {
					@Override
					public int compare(int[] arr1, int[] arr2) {
						return arr2[0] + arr2[1] - arr1[0] - arr1[1];
					}
				});
		int[] tmp = new int[2];
		for (int i = 0; i < nums1.length; i++) {
			for (int j = 0; j < nums2.length; j++) {
				// 每次添加到堆里的对象要不一样
				int[] arr = new int[2];
				arr[0] = nums1[i];
				arr[1] = nums2[j];
				tmp = maxHeap.peek();
				if (maxHeap.size() < k) {
					// System.out.println(Arrays.toString(arr));
					maxHeap.offer(arr);
				} else if ((arr[0] + arr[1]) < (tmp[0] + tmp[1])) {
					maxHeap.poll();
					// System.out.println("---------------");
					// System.out.println(Arrays.toString(arr));
					maxHeap.offer(arr);
				}
			}
		}

		// List<Integer> resTmp = new ArrayList<>();
		List<List<Integer>> res = new ArrayList<>();
		for (int[] ele : maxHeap) {
			// 因为添加的一组数都要和上一次不是同一个对象到
			List<Integer> resTmp = new ArrayList<>();
			// System.out.println("*************");
			// System.out.println(Arrays.toString(ele));
			resTmp.add(ele[0]);
			resTmp.add(ele[1]);
			System.out.println(resTmp);
			res.add(resTmp);
		}
		return res;
	}
}
